package com.atguigu.sort;

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Arrays;

/**
 * @Author : SunFeng
 * @Description: 插入排序
 * 基本思想:把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只包含一个元素，无序表中包含有n-1个元素，
 * 排序过程中每次从无序表中取出第一个元素，把他的排序码依次与有序表元素的排序码进行比较，将他插入有序表的适当位置，使之成为有序表。
 * @Date : 2021/7/1  15:18
 */
public class InsertSort {
    public static void main(String[] args) {
        //int[] array = {10, 3, -1, 9, -2};
        int[] array = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array[i] = (int) (Math.random() * 8000000);
        }
        System.out.println(LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));
        insertSort(array);
        System.out.println(LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));

    }

    /**
     * 当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，
     * 我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。
     * 三个问题
     * 1、插入排序算法的运行不需要额外额存储空间，所以空间复杂度为O(1) 这是一个原地排序算法
     * 2、对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法
     * 3、如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。
     * 所以这种情况下，最好是时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。如果要排序的数据已经是有序的，我们并不需要搬移任何数据。
     * 如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。
     * 所以平均时间复杂度为 O(n2)。
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        // i 是无序列表索引
        for (int i = 1; i < array.length; i++) {
            int insertValue = array[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertValue < array[insertIndex]) {
                // 使有序列表元素后移一个位置
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }

            array[insertIndex + 1] = insertValue;

        }
    }

    public static void insertSort2(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int insertVal = array[i];
            int insertIndex = i - 1;
            for (; insertIndex >= 0; --insertIndex) {
                if (insertVal < array[insertIndex]) {
                    array[insertIndex + 1] = array[insertIndex];
                } else {
                    break;
                }
            }
            array[insertIndex + 1] = insertVal;

        }
    }
}
